2.5

请看以下的正例和反例序列，它们描述的概念是“两个住在同一房间中的人”。每个训练样例描述了一个有序对，每个人由其性别、头发颜色（black、brown 或 blonde）、身高（tall、medium 或 short）以及国籍（US、French、German、Irish、Indian、Chinese 或 Portuguese）。

+ <<male brown tall US>, <female black short US>>
+ <<male brown short French>, <female black short US>>
- <<female brown tall German>, <female black short Indian>>
+ <<male brown tall Irish>, <female brown short Irish>>

考虑在这些实例上定义的假设空间为：所有假设以一对 4 元组表示，其中每个值约束与 Enjoy-Sports 中的假设表示相似，可以为：特定值、“？”或者“ø”。例如，下面的假设：

<<male ? tall ?> <female ? ? French>>

它表示了所有这样的有序对：第一个人为高个男性（国籍和发色任意），第二个人为法国女性（发色和身高任意）。

（a）根据上述提供的训练样例和假设表示，手动执行^{候选消除算法}。特别是要写出处理了每一个训练样例后^变型空间的^特殊和^一般边界。

（b）计算给定的假设空间中有多少假设与下面的正例一致：

+ <<male black short Portuguese> <female blonde tall Indian>>

（c）如果学习器只有一个训练样例，如（b）中所示，现在由学习器提出查询，并由施教者给出其分类。求出一个特定的查询序列，以保证学习器收敛到单个正确的假设，而不论该假设是哪一个（假定目标概念可以使用给定的假设表示语言来描述）。求出最短的查询序列。这一序列的长度与问题（b）的答案有什么关联？

（d）注意到这里的假设表示语言不能够表示这些实例上的所有概念（如我们可定义出一系列的正例和反例，它们并没有相应的可描述假设）。如果要扩展这一语言，使其能够表达该实例语言上的所有概念，那么（c）的答案应该如何更改。

---

解答：

（a）

1. 初始化变型空间：$S_0 = {<<ø, ø, ø, ø>, <ø, ø, ø, ø>>}$, $G_0 = {<<?, ?, ?, ?>, <?, ?, ?, ?>>}$。

2. 处理第一个训练样例：发现 $S_0$ 过于特殊了——因为它不能覆盖该正例。这一步中，$S_0$ 会被一般化为 $S_1 = {<<male\space brown\space tall\space US>, <female \space black \space short \space US>>}$，$G_0$ 边界不需要修改，因为 $G_0$ 能够正确地覆盖该样例。

   训练样例：1. + <<male brown tall US>, <female black short US>>

3. 处理第二个训练样例时，同样需要将 S 进一步一般化到 $S_2$，G 仍旧不变（$G_2=G_1=G_0$）。

   训练样例：2. + <<male brown short French>, <female black short US>>

4. 处理第三个训练样例时，这一反例显示，G 边界过于一般了，需要将 G 进一步特殊化到 $G_3$，S 保持不变。

   训练样例：3. - <<female brown tall German>, <female black short Indian>>

5. 处理第四个训练样例时，变型空间中的 S 边界被更一般化。它也导致 G 边界中的一个成员被删除，因为这个成员不能覆盖新的正例。

   训练样例：4. + <<male brown tall Irish>, <female brown short Irish>>

6. 在处理完这 4 个样例后，边界集合 $S_4$ 和 $G_4$ 划分出的变型空间包含了与样例一致的所有假设的集合。如果提供更多的训练数据，S 和 G 的边界将继续单调移动并相互靠近，划分出越来越小的变型空间来。

   这一变型空间不依赖于训练样本出现的次序（因为最终它包含了与训练样例集一致的所有假设）。

（b）在（a）的结果变型空间中，有 8 个假设，其中 $<<male, ?, ?, ?>, <female, ?, ?, ?>>$ 与新出现的正例一致：+ <<male black short Portuguese> <female blonde tall Indian>>。

（c）如果学习器可以主宰实验进程，它要自己选择一个实例，然后从外界（自然界或者一个施教者）获得该实例的正确分类结果。在这里，我们用查询（query）来代表学习器建立的这个实例，然后由外界来对它分类。

这时学习器怎样能提出一个较好的查询？显然，学习器应试图在当前变型空间中选择假设，以进一步划分该空间。因此，需要选择的实例需要满足：它能被变型空间中的一些假设分类为正例，另一些分类为反例。如果施教者将实例划分为正例，变型空间 S 边界就需要被一般化；如果施教者将实例划分为反例，变型空间 G 边界就需要被特殊化。无论哪种情况，机器将能够学到更多的知识，以确定目标概念并将变型空间缩小到原来的一半。

一般来说，概念学习的最优查询策略，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用 $\lceil log_2|VS| \rceil$ 次实验后得到。当然，在一般情况下，可能无法构造出这样的精确分半的实例，这样，查询的数目可能会大于 $\lceil log_2|VS| \rceil$ 次。

在（b）的答案中我们知道最终的变型空间中有 8 个假设，所以学习器需要提出 3 次查询才能收敛到一个正确的假设。一个可行的查询序列如下：

第一个查询需要满足变型空间的 8 个假设中的 4 个（（b）中的实例就不是一个好的查询，因为它只能满足一个假设），比如：

<<male brown short Portuguese>, <female blond tall Indian>>

就能且仅能满足 4 个假设，即：

<<male ? ? ?>, <? ? ? ?>>
<<male brown ? ?>, <? ? ? ?>> 
<<male ? ? ?>, <female ? ? ?>> 
<<male brown ? ?>, <female ? ? ?>>

这样变型空间就会被缩小到 4 个假设。

假设这个查询被分类为正例，那么变型空间的 S 边界将被一般化（一般成 S₅： {<<male, brown, ?, ?>, <female, ?, ?, ?>>}），G 边界中与这个查询不一致的假设将被删除。这时，变型空间将变为：

这时，学习器需要提出第二个查询，以满足且仅满足这 4 个假设中的 2 个，比如：

<<male brown short Portuguese>, <male blond tall Indian>>

假设这个查询被分类为反例，则变型空间会变成：

接下来，再提出一个查询，比如： <<male black short Portuguese>, <female blond tall Indian>>，就能找到唯一的正确假设。

如果这个查询被分类为正例，那么变型空间将变为：

（d）每个人可能是男性或者女性，头发颜色有 3 种，身高有 3 种可能，而国籍有 7 种可能。因此一个人的特征可能有 $2 \times 3 \times 3 \times 7 = 126$ 种可能。而一个样例是一个有序对，所以有 $126 \times 126 = 15876$ 种可能。这样，我们需要一个 15876 元素的假设空间来表示这些样例。这个假设空间的大小是原来的 1984 倍。这样，学习器需要提出 14 次查询才能收敛到一个正确的假设。